package sort

import (
	"math"
)

type MergeSort struct {
	BaseSort
}

// Sort 归并排序重点是如何让进行归并
func (self MergeSort) Sort() {

	mergeSort(self.Array, 0, self.Len()-1)

}

func mergeSort(array []int, left int, right int) {
	if left >= right {
		return
	}
	mid := (left + right) / 2
	mergeSort(array, left, mid)
	mergeSort(array, mid+1, right)
	merge(array, left, mid, right)

}

// 合并函数，把两个有序的数组合并起来
// arr[left..mif]表示一个数组，arr[mid+1 .. right]表示一个数组
func merge(array []int, left int, mid int, right int) {
	aux := make([]int, right-left+1) //一个新数组，为了暂时存储原数组[left..right]的数据

	if (right + 1 - left) >= 0 {
		for i := left; i <= right; i++ {
			aux[i-left] = array[i]
		}
	}
	//i，j指针为了定位临时数组的位置,方便比较
	i := left    // 定位前半部分元素
	j := mid + 1 //定位后半部分元素

	for k := left; k <= right && i <= right; k++ { //指针k为了定位原数组的位置方便交换
		//防止数组越界
		if i > mid {
			array[k] = aux[j-left]
			j++
		} else if j > right {
			array[k] = aux[i-left]
			i++
		} else
		//比较前端部分元素与后半部分元素大小
		if aux[i-left] < aux[j-left] {
			array[k] = aux[i-left]
			i++
		} else {
			array[k] = aux[j-left]
			j++
		}
	}
}

// MergeSort 自底向上的归并排序
func (self MergeSort) MergeSort() {

	// 循环控制分段
	for segment := 1; segment <= self.Len(); segment = segment * 2 {

		for left := 0; left < self.Len(); left += segment * 2 {
			mid := left + segment - 1
			right := int(math.Min(float64(mid+segment), float64(self.Len()-1))) //比较为了防止数组越界
			merge(self.Array, left, mid, right)
		}
	}
}

func (self MergeSort) Name() string {
	return "归并排序"
}
